/*
 * =====================================================================================
 *
 *       Filename:  N_M_Circle.cc
 *
 *    Description:  you know it
 *
 *        Version:  1.0
 *        Created:  2012年03月26日 10时55分03秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Regan (), lcqhigh@gmail.com
 *        Company:  
 *
 * =====================================================================================
 */

#include	<stdio.h>
#include	<stdlib.h>
#include	<assert.h>
int getLastRemain(int n, int m)
{

    if (n <= 0 || m < 0)
        return -1;
    char *flagarr = new char[n];
    assert(flagarr != NULL);

    for (int i = 0; i < n; ++i)
    {
        flagarr[i] = 1;
    }

    int k = 0, iter = 0;
    int times = n-1;
    while (times)
    {
        if (flagarr[iter] != 0)
            ++k;
        if (k == 3)
        {
            flagarr[iter] = 0;
            k = 0;
            times--;
        }

        ++iter;
        if (iter == n)
            iter = 0;
    }
    
    int res = 0;
    iter = 0;
    while (flagarr[iter] == 0)
        ++iter;
    res = iter++;
    while (iter < n)
    {
        assert(flagarr[iter] == 0);
        ++iter;
    }
    return res;
}

int getLastRemain2(int n, int m)
{
    if (n <= 0 || m < 0)
        return -1;

    int remain = 0;
    for (int i = 2; i <= n; ++i)
    {
        remain = (remain + m) % i;
    }
   
    return remain;
}

void test()
{
    int times = 1000;
    while (times--)
    {
        int n = abs(rand()) % 10000 + 1;
        int m = abs(rand()) % n + 1;
        int idx1 = getLastRemain(n, m);
        int idx2 = getLastRemain2(n, m);
        printf("n:%d, m:%d, idx1:%d, idx2:%d\n", n, m, idx1, idx2);
        assert(idx1 == idx2);
    }
}

int main(int argc, char *argv[])
{
    assert(getLastRemain(2, 3) == 1);
    assert(getLastRemain2(2, 3) == 1);
    assert(getLastRemain(3, 3) == 1);
    assert(getLastRemain2(3, 3) == 1);
    test();
    return 0;
}
